/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;

public class Solution {

    private ArrayList<Integer> in = new ArrayList<>(); 
    private ArrayList<Integer> pre = new ArrayList<>();

    public void preOrder(TreeNode node) {
        if (node == null)
            return ;
        
        pre.add(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(TreeNode node) {
        if (node == null)
            return ;
        
        inOrder(node.left);
        in.add(node.val);
        inOrder(node.right);
    }

    String Serialize(TreeNode root) {
        if (root == null)
            return "";

        preOrder(root);
        inOrder(root);

        return pre.toString();
    }


    private int index = 0;

    public TreeNode dfs(int l, int r) {
        if (l == r)
            return null;
        
        TreeNode node = new TreeNode(pre.get(index));
        int mid = in.indexOf(pre.get(index++));

        node.left = dfs(l, mid);
        node.right = dfs(mid + 1, r);
        return node;
    }

    TreeNode Deserialize(String str) {
        if (str == "")
            return null;

        TreeNode root = new TreeNode(pre.get(index++));
        int mid = in.indexOf(pre.get(0));
        root.left = dfs(0, mid);
        root.right = dfs(mid + 1, pre.size());

        return root;
    }
}